树和二叉树练习题

2024-05-29 11:28| 来源: 网络整理| 查看: 265

文章目录一二叉树的五大性质二判断题三填空题四选择题四分析求解题五算法设计题

一二叉树的五大性质

性质一：对于一颗二叉树，第i层的最大结点数量为 2 i − 1 2^{i-1} 2i−1

性质二：对于一颗深度为k的二叉树，可以具有的最大结点数量为: n = 2 0 + 2 1 + 2 2 + . . . + 2 k − 1 n=2^0+2^1+2^2+...+2^{k-1} n=20+21+22+...+2k−1 简化计算 S n = a 1 × ( 1 − q n ) 1 − q = 1 × ( 1 − 2 k ) 1 − 2 = − ( 1 − 2 k ) = 2 k − 1 S_n=\frac{a_1\times(1-q^n)}{1-q}=\frac{1\times(1-2^k)}{1-2}=-(1-2^k)=2^k-1 Sn=1−qa1×(1−qn)=1−21×(1−2k)=−(1−2k)=2k−1

结论：一颗深度为k的二叉树最大结点数量为 2 k − 1 2^k-1 2k−1,结点的边数为 E = n − 1 E=n-1 E=n−1

性质三：【记忆】 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1

假设一颗二叉树中度为0、1、2的结点数量为 n 0 、 n 1 、 n 2 n_0、n_1、n_2 n0、n1、n2，由于一棵树二叉树中只有这三种类型的结点，可得结点总数： n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0+n1+n2从二叉树的边数考虑，因为每个结点有且仪有一条边与具交结点相连，那么边数之和就可以表示为 E = n 1 + 2 n 2 E=n_1+2n_2 E=n1+2n2度为1的结点有一条边，度为2的结点有两条边，度为0的结点没有，加在一起就是整棵二叉树的边数之和,可得 E = n − 1 = n 1 + 2 n 2 n = n 1 + 2 n 2 + 1 E=n-1=n_1+2n_2 n=n_1+2n_2+1 E=n−1=n1+2n2n=n1+2n2+1再结合第一个公式 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1

性质四：【记忆】

完全二叉树除了最后一层有空缺外，其他层数都是饱满的，假设这模二叉树为满二叉树，那么根据我们前面得到的性质，假设层数为 k k k，那么结点数量为： n = 2 k − 1 n=2^k-1 n=2k−1，根据完全二叉树的性质，最后一层可以满可以不满，那么一棵完全二叉树结点数 n n n满足： 2 k − 1 − 1 < n < = 2 k − 1 2^{k-1}-1//从2开始进行叠加的计算 dp[i]=0;//一开始 //内层循环，计算所有的情况，如i=3,计算dp[0]*dp[2],dp[1]*dp[1],dp[2]*dp[0] for(int j=0;j int res=1; for(int i=2;i if (root!=NULL) { if ((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf ("%d\n",root->data);} DLR (root->lchild); DLR (root->rchild); } Return (0); } 法二： int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 { If (!T) return 0; //空树没有叶子 else if (!T->lchild&&!T->rchild) return 1; //叶子结点 else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数 }//LeafCount_BiTree 写出求二叉树深度的算法。设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。但注意，递归时应当从叶子开始向上计数，否则不易确定层数。 int depth(liuyu*root) /*统计层数*/ { int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0; if(root==NULL)return(p); /*找到叶子之后才开始统计*/ else{ d=depth(root->lchild); if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; } p=p+1; return(p); }

法二：

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 { if(T->data==x) { printf("%d\n",Get_Depth(T)); //找到了值为x的结点,求其深度 exit 1; } } else { if(T->lchild) Get_Sub_Depth(T->lchild,x); if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 } }//Get_Sub_Depth int Get_Depth(Bitree T)//求子树深度的递归算法 { if(!T) return 0; else { m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; } }//Get_Depth 编写按层次顺序（同一层自左至右）遍历二叉树的算法。思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。 Level (liuyu*T) /* liuyu *T,*p,*q[100]; 假设max已知*/ { int f,r; f=0; r=0; /*置空队*/ r=(r+1)%max; q[r]=T; /*根结点进队*/ while(f!=r) /*队列不空*/ { f=(f+1%max); p=q[f]; /*出队*/ printf("%d",p->data); /*打印根结点*/ if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/ if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/ } return(0); }

法二：

void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 编写算法判别给定二叉树是否为完全二叉树。 int IsFull_Bitree (Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 { InitQueue(Q); flag=0; EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { { DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else { EnQueue(Q,p->lchild); EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree

分析：该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.

【本文地址】

公司简介

联系我们